package LargestDivisibleSubset;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
    	List<Integer> result=new ArrayList<>();
    	
    	HashMap<Integer,List<List<Integer>>> map=new HashMap<Integer,List<List<Integer>>>();
    	Arrays.sort(nums);
    	for (int i=0;i<nums.length;i++){
    		List<Integer> temp=null;
    		int maxAns=result.size();
    		for (int j=maxAns;j>=1;j--){
    			List<List<Integer>> list=map.get(j);
    			if (list!=null)
    			for (List<Integer> preList:list)
    				if (nums[i]%preList.get(j-1)==0){
    					List<Integer> newList=new ArrayList<>(preList);
    					newList.add(nums[i]);
    					/*list.remove(preList);*/
    					List<List<Integer>> nextList=map.get(newList.size());
    					if (nextList==null){
    						nextList=new ArrayList<>();
    						map.put(newList.size(), nextList);
    					}
    					nextList.add(newList);
    					temp=newList;
    					break;
    				}
    			if (temp!=null) break;
    		}
            if (temp==null){
            	List<List<Integer>> nextList=(map.get(1)==null?new ArrayList<>():map.get(1));
            	temp=new ArrayList<>();
            	temp.add(nums[i]);
                nextList.add(temp);
                map.put(1, nextList);
            }
    	    if (result.size()<temp.size()) result=temp;
    	}
    	return result;
    }
    
    public static void main(String args[]) {
    	Solution so=new Solution();
    	int[] t={1,2,4,8,9,72};
    	so.largestDivisibleSubset(t);
    	
		
	}
}
